package numFactoredBinaryTrees;

import java.lang.reflect.Array;
import java.net.Inet4Address;
import java.util.*;

public class Solution {
    private static final int MOD = 1000000007;
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        Map<Double,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(1.0*arr[i],i);
        }
        // dp[i]表示以第i个节点为根节点有多少种结果
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n&&arr[j]<arr[i]; j++) {
                double target = 1.0*arr[i]/arr[j];
                int t = map.getOrDefault(target,-1);
                if(t!=-1) {
                    count = (int)(count + (long)dp[t]*dp[j]%MOD)%MOD;
                }
            }
            dp[i] = count;
        }
        int ans = 0;
        for (int d: dp) {
            ans = (ans + d)%MOD;
        }
        return ans;
    }
}